package com.leetcode;

import com.study.common.ListNode;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-17 10:30
 * @version: 1.0
 * @description: 环形链表 II
 *  判断链表是否有环，有则返回环开始的位置
 **/
public class DetectCycle {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1, null);
        ListNode node2 = new ListNode(2, node1);
        ListNode node3 = new ListNode(3, node2);
        ListNode node4 = new ListNode(4, node3);
        ListNode node5 = new ListNode(5, node4);
        ListNode node6 = new ListNode(6, node5);
        ListNode node7 = new ListNode(7, node6);
        ListNode node8 = new ListNode(8, node7);
        node1.next = node5;

        ListNode node = detectCycle(node8);
        System.out.println(node);
    }

    private static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }

        ListNode slow = head, fast = head;
        do{
            slow = slow.next;
            fast = fast.next.next;
            if (fast == null || fast.next == null){
                return null;
            }
        }while (slow != fast);

        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
